package com.leetcode.stack_queue;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Dennis Li
 * @date 2020/7/24 20:50
 */
public class DailyTemperatures_739 {

    public int[] dailyTemperatures2(int[] T) {
        int[] ans = new int[T.length];
        // 记录坐标而不是值
        // 因为求天数是通过坐标求差来解决的，所以考虑保存坐标，而不是值
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < T.length; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int temp = stack.pop();
                ans[temp] = i - temp;
            }
            stack.push(i);
        }
        return ans;
    }


    public int[] dailyTemperatures(int[] T) {
        Deque<Integer> stack = new LinkedList<>();
        int len = T.length;
        int[] res = new int[len];

        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && T[stack.peek()] < T[i]) {
                int pop = stack.pop();
                res[pop] = i - pop;
            }
            stack.push(i);
        }

        return res;
    }

}

